The invention relates to electronic design automation, and more particularly, to methods and apparatuses for rapid checking of design rules in a circuit layout.
Advancements in process technology have impacted integrated circuit manufacturing in at least two key ways. First, scaling of device geometry achieved through sub-wavelength lithography has facilitated packing more devices on a chip. Second, different process recipes have enabled manufacturing of heterogeneous devices with different threshold and supply voltages on the same die. A consequence of these improvements, however, has been an explosion in the number of design rules that need to be obeyed in the layout. Instead of simple width and spacing rules, modern fabrication technologies prescribe complex contextual rules that have to be obeyed for manufacturability.
The increase in the number of rules has complicated the task of creating design rule clean layouts, i.e., layouts that do not have design rule violations. Creating design rule clean layouts for digital circuit designs can be facilitated by the use of standard cell layouts as building blocks, and placement and routing tools that are extended to address the design rules.
Unfortunately, this approach usually does not work for analog, RF and custom circuit designs. Layouts for such designs are typically created manually using layout editors, and because of the number and complexity of the design rules, checking them was a laborious process.
A conventional design rule check (DRC) system requires a powerful two-dimensional geometry engine which supports geometric operations such as Boolean operations like AND, OR, NOT, XOR; sizing operations like grow/shrink horizontal/vertical/diagonal; other operations like merge, shift, flip, cut, smooth; as well as all-angle geometry for true Euclidean distance calculations. Individual rules are typically checked individually over an entire layout region. This is also true of individual rule values of same rule (e.g. a check against the minimum value for a rule, and another check against a preferred value for the same rule). Each check basically runs an independent sequence of geometry operations, and numerous passes through the layout region are required.
For example, a conventional series of operations to check a minimum spacing rule in a Manhattan only layout, might include steps of                Merge all same layer shapes into separate islands;        Grow all islands by half the minimum spacing value;        Perform an AND (intersection) operation among the islands; and        Draw DRC violation markers based on the resulting shapes of the AND operation.        
As another example, a conventional series of operations to check a minimum width rule in a Manhattan only layout, might include steps of                Merge all same layer shapes into separate islands;        Shrink all islands by (half the minimum width value+epsilon)        Eliminate all resulting islands of zero area;        Grow back the resulting islands by (half the minimum width value+epsilon);        Perform a NOT operation between the original merged islands and grown back islands; and        Draw DRC violation markers based on the shapes resulting from the NOT operation.        
So long as a good geometry engine is available, the conventional DRC techniques are simple to code, at least for simple rules. They are also flexible and powerful if the geometry engine has a scripting API for relevant geometry operations, and it is relatively straightforward to massively parallelize the DRC process among numerous CPUs.
On the other hand, it can be seen that checking even simple design rules like those above is extremely expensive computationally. Massive parallelization usually is possible only for offline checks, which typically are performed only between layout iterations. Even then they often can require hours to complete. The conventional approach also suffers from roughly linear growth of the total run time with respect to the number of rules to be checked, with multiple values for a rule counted as separate rules. This makes it very hard to reduce the total run time without turning off selected rules. The conventional approach also suffers from linear growth of run time for individual rule checks, with respect to the length of the geometry operation sequence, i.e., the complexity of the rule. The conventional approach also involves separate checks for Euclidean measurements, and also requires extensive education and training in order to optimize the performance of the customer scripts.
Recently, the march toward increasingly smaller technology nodes has pushed fabrication vendors to support double-patterning technology (DPT). If integrated circuit features on a layer are laid out too near each other for adequate separation when exposed through a lithographic mask, then the features are apportioned onto two different masks, each mask having only some of the features for the layer. During fabrication, the wafer is exposed twice, once with each mask. In this way features can be defined on the integrated circuit which are too finely spaced for them to be defined clearly and reliably by a single mask. Double-patterning technology can be extended to triple-patterning technology, in which the features for a layer are apportioned onto three different masks, and so on. Apportionment onto higher numbers of masks is possible as well, and these techniques are sometimes referred to generally as “multi-patterning technology”.
Typically the mask fabricator (which often is also the chip fabricator) uses its own algorithm to allocate shapes among the two or more masks. However, in some arrangements of layout shapes an allocation is not possible since a particular shape cannot be allocated to any of the masks without violating the spacing rules for features on that mask. In a layout layer which has not yet been split, these situations can be detected by a design rule checking algorithm which assigns different “colors” (corresponding to different lithographic masks) to any pair of shapes which are nearer to each other than the minimum multi-patterning spacing constraint for a single mask. Chains of such features are detected, each feature forcing the next feature to have a different color. In the double-patterning case, each next feature is assigned the color opposite to the former feature in the chain. In the multi-patterning case multiple colors are used, and it is sufficient that each next feature be assigned a different (also called non-conflicting) color.
If a chain loops back onto itself, then it forms a “cycle”. A cycle is not itself bad, unless there is no way to avoid two adjacent features in the chain being assigned the same color. In the double-patterning situation, if a cycle contains an even number of features, then there is no conflict because a color conflict can be avoided. The arrangement can then be allocated among the two masks without violating the single-mask spacing rules. If a cycle contains an odd number of features in the double-patterning case, however, then a coloring conflict exists and the arrangement, if not modified, cannot be allocated among the two masks without violating the single-mask spacing rules. The latter situation is sometimes referred to herein as a “DPT odd cycle violation”. (In the extension to multi-patterning, coloring conflicts are sometimes referred to herein as “multi-patterning coloring violations”.)
A number of techniques exist for handling odd cycle violations. But if none of them work, then one or more of the features must be moved away from one or more other features, in order to break the cycle. Since this solution can reduce circuit density, it would be desirable to move features only so far as needed in order to solve the problem. For a manual layout editor, this would ideally involve real time DPT odd cycle detection, so that after every movement or other edit of a shape the user can see immediately whether the violation remains. But checking for DPT odd cycle violations can be extremely time consuming by conventional methods, and prohibitively slow for such real time layout editing.